package demo.oo.trains;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

public class RouteManager {
	private static final Logger LOGGER = Logger.getLogger(RouteManager.class);

	private Map<String, List<Edge>> startPointEdgesMap = new HashMap<String, List<Edge>>();
	private List<Edge> allRoutes = new ArrayList<Edge>();
	private String defaultStartPoint;

	public RouteManager(String routesInfo) {
		buildRoutes(routesInfo);
	}

	public void tranverse(RouteProcessor routeProcessor) {
		if (defaultStartPoint == null)
			return;

		Set<Edge> tranversedEdges = new HashSet<Edge>(allRoutes.size());
		for (Edge startEdge : startPointEdgesMap.get(defaultStartPoint)) {
			tranverse(startEdge, tranversedEdges, routeProcessor);
		}
	}

	public List<Path> findPaths(String startPoint, String endPoint) {
		List<Path> paths = new ArrayList<Path>();

		List<Edge> startRouteSet = startPointEdgesMap.get(startPoint);
		if (startRouteSet == null) {
			return paths;
		}

		for (Edge startEdge : startPointEdgesMap.get(startPoint)) {
			tranverse(startEdge, new HashSet<Edge>(), new PathFinder(startPoint, endPoint, paths));
		}

		return paths;
	}

	private class PathFinder implements RouteProcessor {
		private String startPoint;
		private String endPoint;
		private List<Path> paths;
		private Path path;

		/**
		 * PathFinder will find all available paths between startPoint and
		 * endPoint. The found path will put into paths.
		 * 
		 * @author lifany
		 * 
		 */
		private PathFinder(String startPoint, String endPoint, List<Path> paths) {
			this.startPoint = startPoint;
			this.endPoint = endPoint;
			this.paths = paths;
			path = new Path(startPoint, endPoint);
		}

		@Override
		public boolean process(Route route) {
			if (path.isComplete()) {
				LOGGER.debug("Path: [" + path + "] is completed.");
				LOGGER.debug("Try to build a new path based on it.");

				Path newPath = new Path(startPoint, endPoint);

				for (Route routeInPath : path.getRoutes()) {
					LOGGER.debug("Add " + routeInPath + " into the new path.");
					newPath.getRoutes().add(routeInPath);

					if (routeInPath.getEndPoint().equals(route.getStartPoint())) {
						break;
					}
				}

				path = newPath;
			}

			path.getRoutes().add(route);

			if (route.getEndPoint().equals(endPoint)) {
				LOGGER.debug("Add Path [" + path + "] into the final set.");
				paths.add(path);
				return true;
			}

			return false;
		}
	}

	/**
	 * Depth-first
	 * 
	 * @param route
	 * @param processedRoutes
	 * @param routeProcessor
	 */
	private void tranverse(Edge route, Set<Edge> processedRoutes, RouteProcessor routeProcessor) {
		if (processedRoutes.contains(route)) {
			LOGGER.debug("Route " + route + " has been processed.");
			return;
		}

		boolean stop = routeProcessor.process(route);
		if (stop) {
			return;
		}

		processedRoutes.add(route);

		if (route.getNextEdges() == null)
			return;

		for (Edge nextRoute : route.getNextEdges()) {
			tranverse(nextRoute, processedRoutes, routeProcessor);
		}
	}

	/**
	 * Input like: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
	 * 
	 * @param routesInfo
	 */
	private void buildRoutes(String routesInfo) {
		for (String routeInfo : routesInfo.split(",")) {
			addRoute(routeInfo.trim());
		}

		buildRouteNet();
	}

	private void buildRouteNet() {
		for (Edge route : allRoutes) {
			List<Edge> nextRoutes = startPointEdgesMap.get(route.getEndPoint());
			if (nextRoutes != null)
				route.getNextEdges().addAll(nextRoutes);
		}
	}

	private void addRoute(String routeInfo) {
		String startPoint = getStartPoint(routeInfo);
		String endPoint = getEndPoint(routeInfo);
		int length = getRouteLength(routeInfo);
		Edge edge = new Edge(startPoint, endPoint, length);

		allRoutes.add(edge);
		addToStartPointEdgesMap(startPoint, edge);

		if (defaultStartPoint == null) {
			defaultStartPoint = edge.getStartPoint();
		}
	}

	private void addToStartPointEdgesMap(String key, Edge route) {
		List<Edge> routes = startPointEdgesMap.get(key);
		if (routes == null) {
			routes = new ArrayList<Edge>();
			startPointEdgesMap.put(key, routes);
		}
		routes.add(route);
	}

	private String getStartPoint(String routeInfo) {
		return routeInfo.substring(0, 1);
	}

	private String getEndPoint(String routeInfo) {
		return routeInfo.substring(1, 2);
	}

	private int getRouteLength(String routeInfo) {
		String lenStr = routeInfo.substring(2, routeInfo.length());
		return Integer.parseInt(lenStr);
	}
}
